package com.peng.leetcode.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * FindMode
 * 501. 二叉搜索树中的众数
 * https://leetcode.cn/problems/find-mode-in-binary-search-tree/
 * <p>
 * Created on 2022/12/7
 *
 * @author lupeng
 */
public class FindMode {
    public int[] findMode(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        dfs(root);
        List<Integer> ans = new ArrayList<>();
        val2countMap.forEach((v, c) -> {
            if (c == maxCount) {
                ans.add(v);
            }
        });
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }

    Map<Integer, Integer> val2countMap = new HashMap<>();
    int maxCount = 0;

    void dfs(TreeNode n) {
        if (n == null) {
            return;
        }
        int count = val2countMap.getOrDefault(n.val, 0) + 1;
        val2countMap.put(n.val, count);
        maxCount = Math.max(maxCount, count);
        dfs(n.left);
        dfs(n.right);
    }
}
